package io.github.hadyang.leetcode.offer;

import java.util.Arrays;
import org.junit.Test;

/** @author haoyang.shi */
public class MaxGift {

  @Test
  public void test() {
    System.out.println(
        maxGift(
            new int[][] {
              {1, 10, 3, 8},
              {12, 2, 9, 6},
              {5, 7, 4, 11},
              {3, 7, 16, 5},
            }));
  }

  public int maxGift(int[][] matrix) {
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[i].length; j++) {
        int a = i > 0 ? matrix[i - 1][j] : 0;
        int b = j > 0 ? matrix[i][j - 1] : 0;

        matrix[i][j] += Math.max(a, b);
      }
    }

    System.out.println(Arrays.deepToString(matrix));

    return matrix[matrix.length - 1][matrix[0].length - 1];
  }
}
